In an effort to increase the processing speed and flexibility of supercomputers, the cluster architecture for highly parallel multiprocessors described in the previously identified parent application, Ser. No. 07/459,083, provides an architecture for supercomputers wherein multiple of processors and external interfaces can make multiple and simultaneous requests to a common set of shared hardware resources, such as main memory, global registers or interrupt mechanisms.
One of the important limitations in designing such a cluster architecture is providing a fair and efficient method and apparatus for prioritizing requests to multiple shared resources by multiple requestors, in this case requests by multiple processors to common shared resources in a highly parallel multiprocessor system. Prior art methods and systems for determining the priority among multiple competing requestors to common shared resources are inadequate to meet the needs of such a cluster architecture.
It is recognized that a computer or electronic logic system which communicates with a shared resource requires a switching network. This implies that conflicts can occur when multiple requestors are attempting to simultaneously access the shared resource. Consequently, some type of arbitration algorithm must be employed to determine which requestor is to be granted access to the destination resource having conflicting requests. A fair and efficient system must satisfy at least the following goals: (1) any free resource will always receive a grant if there is at least one valid request attempting to access it; (2) relative time ordering of requests is maintained (i.e., access is granted on a first come first serve basis); (3) equal access to all resources is provided for each requestor (i.e., "fairness" is ensured when arbitrating among requestors); (4) wait time during requestor conflicts is minimized; and (5) arbitration control decision time is minimized.
Although several types of arbitration algorithms exist in the prior art, the traditional prior art arbitration algorithms are not effective at meeting these goals. Two of the more common prior art arbitration algorithms are the Round Robin and the Priority Ring.
Round Robin is a prior art technique that gives each requestor an opportunity to be the highest priority. This opportunity is given to each requestor, one at a time through a rotating mechanism. The problem associated with this is that a requestor's priority is unrelated to when the request is actually made. In other words, the requestor might have been rotated to lowest priority just prior to the request. Thus, subsequent requests are serviced prior to the original one. This fails to satisfy goals 2 and 4 set forth above.
A Priority Ring is another prior art arbitration technique. This scheme gathers requests made over a given time period into a group or "ring". At the end of the time period, the ring is closed and all requests that have been stored in this ring are processed according to a fixed priority resolution mechanism. While the requests that were gathered into the first ring are processed, subsequent requests are gathered into a new ring. When all of the requests in the first ring have been processed, the second ring is closed, and the first ring is free to accept new requests. The problem associated with this technique is that a given requestor always has a fixed priority relative to the other requestors within each ring. Thus, the algorithm favors certain requests over others and it allows later requests to be granted before previous ungranted requests, thereby failing to satisfy goals 2, 3 and 4 set forth above.
Because of the inherent limitations of the present methods and systems for determining the priority among multiple competing requestors to common shared resources, it is not possible to fairly and efficiently prioritize such requests in a manner that allows for requestors to be serviced on a first-come, first-served basis. Therefore, a new method and apparatus for a multiple request toggling priority system is needed that provides for a fair and efficient prioritization of multiple simultaneous requests in a single clock cycle.